// https://www.lintcode.com/problem/32/

class Solution {
public:
    /**
     * @param source : A string
     * @param target: A string
     * @return: A string denote the minimum window, return "" if there is no such a string
     */
    // map里直接就减成负数，这样也能记录source里面的情况，不用根据target来判断左指针移动的时候需不需要改map
    string minWindow(string &source , string &target) {
        map<char, int> rec;
        int sum = 0;
        int start = 0;
        int end = 0;
        int min_len = INT_MAX;
        int res_start = 0;
        for (char c: target) {
            rec[c]++;
        }
        while (end < source.length()) {
            char c = source[end];
            rec[c]--;
            if (rec[c] >= 0) sum++;
            while (sum == target.length()) {
                if (end - start + 1 < min_len) {
                    min_len = end - start + 1;
                    res_start = start;
                }
                rec[source[start]]++;
                if (rec[source[start]] > 0) sum--;
                start++;
            }
            // } else {
            end++;
            // }
        }
        // return source.substr(res_start, min_len);
        if (min_len != INT_MAX) return source.substr(res_start, min_len);
        else return "";
    }
};